IMPROVEMENT AND ASSESSMENT OF LI-OPENSHAW ALGORITHM

K. Zhu, F. Wu, H. Wang, Q. Zhu

Institute of Surveying and Mapping, Information Engineering University, Zhengzhou, China

zhkp417@126.com

Li-Openshaw algorithm is a self-adapted linear feature’s generalization algorithm based on impersonality generalized natural law, and it can get reasonable and genuine generalization results. On the basis of analyzing characteristics of Li-Openshaw algorithm, there are two flaws in the algorithm: ①without referring to save local maximum points, the algorithm doesn’t keep the entire shape of curve well;②abnormity happened easily in selection when there are more than one point of intersection between SVO circularity and curve, and coordinates of selected points need to be calculated, which will decrease the simplification efficiency. According to the principle and purpose of linear simplification, Li-Openshaw algorithm is improved as follow: ①a new method of identifying the bend using the relationship between point and line is proposed, in order to find all the local maximum points and save to keep the entire shape of curve before simplification; ②find the first approximate point of intersection according to lines’ index, then select the point to save after generalization, which is nearest to the midpoint between center point of circle and point of intersection on the curve. What’s more, evaluating figures such as simplification results, time for simplification and ratio of compressing points are given, especially, two algorithms are compared and assessed by the method of curves’ shape structure characteristic assessment based on fractal theory. According to experiments’ results, compared with original algorithm, improved algorithm can keep the entire shape of curve better and increase simplifying efficiency.